package algo.couterbased;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import algorithm.AbstractCounterBased;

public class SpaceSaving extends AbstractCounterBased {
	
	public SpaceSaving() {
		super("SpaceSaving");
	}

	public Map<Object, Double> compute(int[] stream) {

		size = 0;
		List<Object> t = new ArrayList<Object>();
		result = new HashMap<Object, Double>();

		for (Object item : stream) {
			size++;
			if (t.contains(item)) {
				result.put(item, result.get(item) + 1);
			} else if (t.size() < stream.length) {
				t.add(item);
				result.put(item, 1.0);
			} else {
				Object current_minimum_object = getSmallestObject(t, result);
				if (current_minimum_object != null) {
					result.put(item, result.get(current_minimum_object) + 1);
					t.remove(current_minimum_object);
				} else
					result.put(item, 1.0);
			}
		}

		return result;
	}

	public static Object getSmallestObject(List<Object> t,
			Map<Object, Double> res) {

		Object minObject = null;
		for (Object o : t) {
			if (minObject == null || res.get(o) < res.get(minObject))
				minObject = o;
		}
		return minObject;
	}
}
